//动态规划

//思路一
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //1.创建dp表

        //2.状态表示：dp[i]表示以i为终点，需要最小的费用
        
        //4.确定方程：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

        //5.初始化:dp[0]==dp[1]=0

        //6.填表顺序 ：从左到右

        //6.返回值:dp[i]
        int n=cost.size();
        vector<int> dp(n+1);
        dp[0]=dp[1]=0;
        for(int i=2;i<=n;i++)
        {
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
};

//思路2
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //1.创建dp表

        //2.状态表示：dp[i]表示以i为起点，到顶需要最小的费用
        
        //4.确定方程：dp[i]=cost[i]+min(dp[i+1],dp[i+2])

        //5.初始化:dp[i-1]=cost[i-1],dp[i-2]=cost[i-2]

        //6.填表顺序 ：从右向左

        //6.返回值:min(dp[0],dp[1])
        int n=cost.size();
        vector<int> dp(n+1);
        dp[n-1]=cost[n-1],dp[n-2]=cost[n-2];
        for(int i=n-3;i>=0;i--)
        {
            dp[i]=cost[i]+min(dp[i+1],dp[i+2]);
        }
        return min(dp[0],dp[1]);
    }
};